/* 动态规划相关操作:
斐波那契数列
矩阵的最小路径和
换钱的最少货币数（每个数字可以用多次）
换钱的方法数（每一面值不限张数）
最长公共子序列问题
最长公共子串
N皇后问题
 */
 
//斐波那契数列
public int f1(int n){
	if(n<1){
		return 0;
	}
	if(n==1 || n==2){
		return 1;
	}
	return f1(n-1)+f2(n-2);
}
public int f2(int n){
	if(n<1){
		return 0;
	}
	if(n==1 ||n==2){
		return 1;
	}
	int res=1;
	int pre=1;
	int tmp=0;
	for(int i=3;i<=n;i++){
		temp = res;
		res = res+pre;
		pre = temp;
	}
	return res;
}

//矩阵的最小路径和
public int minPathSum1(int[][] m){
	if(m==null || m.length==0 || m[0]==null ||m[0].length ==0){
		return 0;
	}
	int row = m.length;
	int col = m[0].length;
	int[][] dp = new int[row][col];
	dp[0][0] = m[0][0];
	for(int i=1;i<row;i++){
		dp[i][0] = dp[i-1][0]+m[i][0];
	}
	for(int j=1;j<col;j++){
		dp[0][j] = dp[0][j-1]+m[0][j];
	}
	for(int i=1;i<row;i++){
		for(int j=1;j<col;j++){
			dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+m[i][j];
		}
	}
	return dp[row-1][col-1];
}

//换钱的最少货币数（每个数字可以用多次）
public int minCoins1(int[] arr,int aim){
	if(arr ==null || arr.length==0 ||aim <0){
		return -1;
	}
	int n = arr.length;
	int max = Integer.MAX_VALUE;
	int[][] dp = new int[n][aim+1];
	for(int i=0;i<n;i++){
		dp[i][0]=0;
	}
	for(int j=1;j<=aim;j++){
		dp[0][j] = max;
		if(j-arr[0]>=0 && dp[0][j-arr[0]]!=max){
			dp[0][j] = dp[0][j-arr[0]]+1;
		}
	}
	int left = 0;
	for(int i =1; i<n;i++){
		for(int j=1;j<=aim;j++){
			left =max;
			if(j-arr[i]>=0 && dp[i][j-arr[i]]!=max){
				left = dp[i][j-arr[i]]+1;
			}
			dp[i][j] = Math.min(left,dp[i-1][j]);
		}
	}
	return dp[n-1][aim] != max ? dp[n-1][aim]:-1;
}

//换钱的最少货币数（每个数字只能用一次）
public int minCoins2(int[] arr, int aim){
	if(arr==null arr.length==0||aim<0){
		return -1;
	}
	int n = arr.length;
	int max = Integer.MAX_VALUE;
	int[][] dp = new int[n][aim+1];
	for(int i =0;i<n;i++){
		dp[i][0]=0;
	}
	for(int j=1;j<=aim;j++){
		dp[0][j] =max;
	}
	if(arr[0]<=aim){
		dp[0][arr[0]]=1;
	}
	int leftup = 0;
	for(int i=1;i<n;i++){
		for(int j=1;j<=aim;j++){
			leftup = max;
			if(j-arr[i]>=0 && dp[i-1][j-arr[i]]!=max){
				leftup = dp[i-1][j-arr[i]]+1;
			}
			dp[i][j] = Math.min(leftup,dp[i-1][j]);
		}
	}
	return dp[n-1][aim] != max?dp[n-1][aim]:-1;
}

//换钱的方法数（每一面值不限张数）
public int coins3(int[] arr, int aim){
	if(arr==null || arr.length==0 || aim<0){
		return 0;
	}
	int[][] dp = new int[arr.length][aim+1];
	for(int i=0;i<arr.length;i++){
		dp[i][0]=1;
	}
	for(int j=1;j<=aim;j++){
		dp[0][j] = j%arr[0]==0 ?1:0;
	}
	for(int i=1;i<arr.length;i++){
		for(int j=1;j<=aim;j++){
			dp[i][j]=dp[i-1][j];
			dp[i][j]+=j-arr[i]>=0?dp[i][j-arr[i]]:0;
		}
	}
	return dp[arr.length-1][aim];
}

//最长公共子序列问题
public int[][] getdp(char[] str1,char[] str2){
	int[][] dp = new int[str1.length][str2.length];
	dp[0][0] = str1[0]==str2[0] ?1:0;
	for(int i=1;i<str1.length;i++){
		dp[i][0]=Math.max(dp[i-1][0],str1[i]==str2[0]?1:0);
	}
	for(int j=1;j<str2.length;j++){
		dp[0][j]=Math.max(dp[0][j-1],str1[0]==str2[j]?1:0);
	}
	for(int i=1;i<str1.length;i++){
		for(int j=1;j<str2.length;j++){
			dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
			if(str1[i]==str2[j]){
				dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
			}
		}
	}
	return dp;
}
public String lcse(String str1,String str2){
	if(str1 ==null ||str2 ==null ||str1.equals("")||str2.equals("")){
		return "";
	}
	char[] chs1 = str1.toCharArray();
	char[] chs2 = str2.toCharArray();
	int[][] dp = getdp(chs1,chs2);
	int m = chs1.length-1;
	int n = chs2.length-1;
	char[] res = new char[dp[m][n]];
	int index = res.length -1;
	while(index>=0){
		if(n>0 &&dp[m][n]==dp[m][n-1]){
			n--;
		}else if(m>0&&dp[m][n]==dp[m-1][n]){
			m--;
		}else{
			res[index--]=chs1[m];
			m--;
			n--;
		}
	}
	return String.valueOf(res);
}

//最长公共子串
public int[][] getdp(char[] str1, char[] str2){
	int[][] dp = new int[str1.length][str2.length];
	for(int i=0;i<str1.length;i++){
		dp[i][0] = str1[i]==str2[0]?1:0;
	}
	for(int j=0;j<str2.length;j++){
		dp[0][j] = str1[0]==str2[j]?1:0;
	}
	for(int i=1;i<str1.length,i++){
		for(int j=1;j<str2.length;j++){
			dp[i][j] = str1[i]==str2[j]?dp[i-1][j-1]+1:0;
		}
	}
	return dp;
}
public String lcst1(String str1,String str2){
	if(str1==null||str2==null||str1.equals("")||str2.equals("")){
		return "";
	}
	char[] chs1 = str1.toCharArray();
	char[] chs2 = str2.toCharArray();
	int[][] dp = getdp(chs1,chs2);
	int end = 0;
	int max = 0;
	for(int i=0;i<chs1.length;i++){
		for(int j=0;j<chs2.length;j++){
			if(dp[i][j]>max){
				end = i;
				max = dp[i][j];
			}
		}
	}
	return str1.subString(end-max+1,end+1);
}
public String lcst2(String str1,String str2){
	if(str1==null||str2==null||str1.equals("")||str2.equals("")){
		return "";
	}
	char[] chs1 = str1.toCharArray();
	char[] chs2 = str2.toCharArray();
	int row=0;
	int col=chs2.length-1;
	int max = 0;
	int end = 0;
	while(row<chs1.length){
		int i=row;
		int j=col;
		int len = 0;
		while(i<chs1.length&&j<chs2.length){
			if(chs1[i]!=chs2[j]){
				len=0;
			}else{
				len++;
			}
			if(len>max){
				end=i;
				max=len;
			}
			i++;
			j++;
		}
		if(col>0){
			col--;
		}else{
			row++;
		}
	}
	return str1.subString(end-max+1,end+1);
}

//N皇后问题
public int num(int n){
	if(n<1){
		return 0;
	}
	int[] record= new int[n];
	return process1(0,record,n);
}
public int process1(int i, int[] record, int n){
	if(i==n){
		return 1;
	}
	int res = 0;
	for(j =0;j<n;j++){
		if(isValid(record,i,j)){
			record[i]=j;
			res += process1(i+1,record,n);
		}
	}
	return res;
}
public boolean isValid(int[] record,int i,int j){
	for(k=0;k<i;k++){
		if(j==record[k]||Math.abs(record[k]-j)==Math.abs(i-k)){
			return false;
		}
	}
	return true;
}






















	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
}